package 二叉树;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-12-25
 **/

public class No1609奇偶树 {

    public boolean isEvenOddTree(TreeNode root) {

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);

        // 是否为奇数
        boolean isOdd = false;

        while (!deque.isEmpty()) {


            int count = deque.size();
            TreeNode firstNode = deque.removeFirst();
            count--;
            int lastNum = firstNode.val;
            if (isOdd) {
                // 奇数 整层都是偶数值,并且从左起递减
                if (lastNum % 2 != 0) {
                    return false;
                }
            } else {
                // 偶数 整层都是奇数值,并且从左起递增
                if (lastNum % 2 == 0) {
                    return false;
                }
            }
            this.addNode(deque, firstNode);

            while (count > 0) {

                TreeNode treeNode = deque.removeFirst();
                if (isOdd) {
                    // 奇数 整层都是偶数值,并且从左起严格递减
                    if (treeNode.val % 2 != 0 || lastNum <= treeNode.val) {
                        return false;
                    }
                } else {
                    // 偶数 整层都是奇数值,并且从左起严格递增
                    if (treeNode.val % 2 == 0 || lastNum >= treeNode.val) {
                        return false;
                    }
                }
                this.addNode(deque, treeNode);
                lastNum = treeNode.val;
                count--;
            }

            isOdd = !isOdd;
        }

        return true;
    }

    private void addNode(Deque<TreeNode> deque, TreeNode node) {
        if (node.left != null) {
            deque.addLast(node.left);
        }
        if (node.right != null) {
            deque.addLast(node.right);
        }
    }

    public static void main(String[] args) {
        No1609奇偶树 n = new No1609奇偶树();
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{13, 34, 32, 23, 25, 27, 29, 44, 40, 36, 34, 30, 30, 28, 26, 3, 7, 9, 11, 15, 17, 21, 25, null, null, 27, 31, 35, null, 37, null, 30, null, 26, null, null, null, 24, null, 20, 16, 12, 10, null, null, 8, null, null, null, null, null, 6, null, null, null, null, null, 15, 19, null, null, null, null, 23, null, 27, 29, 33, 37, null, null, null, null, null, null, 48, null, null, null, 46, null, null, null, 42, 38, 34, 32, null, null, null, null, 19});
        nodeByArr.printNode();
        boolean evenOddTree = n.isEvenOddTree(nodeByArr);
        System.out.println(evenOddTree);
    }

}
